package search

// DfsRecursive 深度优先遍历 递归版
func (bt *BinaryTreeNode) DfsRecursive(order OrderEnum) []int32 {
	res := make([]int32, 0)
	fn := order.GetDfdRecursiveFunc()
	res = fn(bt, res)
	return res
}

func dfsRecursiveFront(curNode *BinaryTreeNode, curArray []int32) []int32 {
	if curNode == nil {
		return curArray
	}

	curArray = append(curArray, curNode.Val)
	curArray = dfsRecursiveFront(curNode.Left, curArray)
	curArray = dfsRecursiveFront(curNode.Right, curArray)

	return curArray
}
func dfsRecursiveMiddle(curNode *BinaryTreeNode, curArray []int32) []int32 {
	if curNode == nil {
		return curArray
	}
	curArray = dfsRecursiveMiddle(curNode.Left, curArray)
	curArray = append(curArray, curNode.Val)
	curArray = dfsRecursiveMiddle(curNode.Right, curArray)
	return curArray
}
func dfsRecursiveBack(curNode *BinaryTreeNode, curArray []int32) []int32 {
	if curNode == nil {
		return curArray
	}
	curArray = dfsRecursiveBack(curNode.Left, curArray)
	curArray = dfsRecursiveBack(curNode.Right, curArray)
	curArray = append(curArray, curNode.Val)
	return curArray
}

type BinaryTreeNode struct {
	Val   int32
	Left  *BinaryTreeNode
	Right *BinaryTreeNode
}

type OrderEnum int

const (
	// OrderFront 前序 中左右
	OrderFront OrderEnum = 1
	// OrderMiddle 中序 左中右
	OrderMiddle OrderEnum = 2
	// OrderBack 后序 左右中
	OrderBack OrderEnum = 3
)

func (o OrderEnum) GetDfdRecursiveFunc() func(curNode *BinaryTreeNode, curArray []int32) []int32 {
	switch o {
	case OrderFront:
		return dfsRecursiveFront
	case OrderMiddle:
		return dfsRecursiveMiddle
	default:
		return dfsRecursiveBack
	}
}
